package com.cskaoyan.javase.recursion._2hanoi;

/**
 * 汉诺塔（Hanoi）问题，是经典的递归问题，学习递归一般都绕不开它，这里我们就学习一下如何使用递归求解汉诺塔问题。
 *
 * 首先看一下汉诺塔问题的描述：
 * 相传在古印度的圣庙中，有一种被称之为汉诺塔（也叫河内塔，Hanoi）的游戏
 * 简单来说：有三个塔1，2，3，塔1上有 N 个（N>1）穿孔圆盘，大盘在下，小盘在上
 * 要求按下列规则将所有圆盘移至塔3：
 * 	1，每次只能移动一个圆盘
 * 	2，大盘一定在小盘之下
 * 提示：可将圆盘临时置于塔2，也可以将塔1的圆盘重新移回塔1，但都必须遵循上述两条规则
 * 问：当塔1上有N（N>=1）个圆盘时，最少要移动多少次？（注意是最少）
 *
 * 设完成N个圆盘的汉诺塔问题,最少要移动f(N)次
 * 完成N个圆盘的汉诺塔问题,必不可少的一步是:
 *      将塔1上最大的盘子,移到塔3上去,这时塔3必须是空的,而且除了最大盘子外的所有盘子都必须在塔2上.
 *      要想完成以上状态,必须将N-1个盘子,从塔1移到塔2,这个过程可以借助塔3来完成,但最终要保证塔3是空着的.(这就是N-1个盘子的汉诺塔问题)
 *      现在将塔1上最大的盘子移到了塔3上,于是只要将N-1个盘子,从塔2移到塔3,就能够完成N个盘子的汉诺塔问题(这就是N-1个盘子的汉诺塔问题)
 *      也就是说,完成N个盘子的汉诺塔问题,最少需要f(N)步,可以分解为:
 *          1.将N-1个盘子,从塔1移到塔2,借助塔3完成,共需要f(N-1)步
 *          2.将塔1上最大的盘子移到了塔3上,共需要1步
 *          3.将N-1个盘子,从塔2移到塔3,需要借助塔1来完成,共需要f(N-1)步
 *       所以:
 *          f(N) = f(N-1) + 1 + f(N-1)
 *          以上就是一个分解得到的表达式,其实就是递归体
 *          而且f(1) = 1,这是递归的出口
 *
 * 已知f(N) = f(N-1) + 1 + f(N-1),求f(N)的通项公式
 * f(N) = 2f(N-1) + 1;
 * f(N)  + 1 = 2( f(N-1) + 1 )
 * f(N) + 1 / ( f(N-1) + 1 ) = 2
 * f(N) + 1  = 2 ^ N
 * f(N)  = 2 ^ N - 1;
 *
 * @since 15:12
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(hanoi(10));
    }

    public static long hanoi(int n) {
        // 递归的出口
        if (n == 1) {
            return 1;
        }
        return hanoi(n - 1) + 1 + hanoi(n - 1);
    }
}
